package com.Sep_Twenty;

import java.util.ArrayList;
import java.util.List;

public class Solution216 {

    static List<List<Integer>> list=new ArrayList<>();
    static List<Integer> path=new ArrayList<>();

    public static List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(n,k,1,0);
        return list;
    }

    public static void backtracking(int targetSum, int n, int startIndex, int sum){
        if (sum>targetSum) return;
        if (path.size()==n)
        {
            if (sum==targetSum)
            {
                list.add(new ArrayList<>(path));
            }
        }
        for (int i=startIndex;i<=9;i++)
        {
            //sum+=i;
            path.add(i);
            backtracking(targetSum,n,i+1,sum+i);
            path.remove(path.size()-1);
        }
    }

    public static void main(String[] args) {
        System.out.println(combinationSum3(3,9));
    }
}
